﻿#include "long_int_t.h"

namespace
{
   size_t length(long long value)
   {
      size_t result = 0;
      while (value != 0)
      {
         result++;
         value /= 10;
      }

      if (result != 0)
      {
         return result;
      }
      else
      {
         return 1;
      }
   }
}

long_int_t::long_int_t(void) : shift_(0), digits_(std::vector<long long>(1, 0))
{  
}

long_int_t::long_int_t(long long value) : shift_(0)
{   
   if (value == 0)
   {
      digits_.push_back(0);
      return;
   }
   while (value > 0)
   {
      digits_.push_back(value % BASE);
      value /= BASE;
   }
}

long_int_t long_int_t::zero()
{
   return long_int_t(0);
}

std::istream& operator>>(std::istream& is, long_int_t& result)
{
   std::string str;
   if (!(is >> str))
   {
      return is;
   }

   result.digits_.clear();
   result.shift_ = 0;

   size_t length = str.length();
   int size =  length / long_int_t::BASE_LENGTH;
   int end = length % long_int_t::BASE_LENGTH;
   if (end != 0)
   {
      size++;
   }
   result.digits_.resize(size);

   int current = 0, position = 0, index = size - 1;

   for (size_t i = 0; i < length; i++)
   {
      if (i % long_int_t::BASE_LENGTH == end && position != 0)
      {
         result.digits_[index--] = current;
         current = 0;
         position = 0;
      }
      
      current = current * 10 + str[i] - '0';
      position++;
   }

   result.digits_[index] = current;

   return is;
}

std::ostream& operator<<(std::ostream& os, const long_int_t& value)
{
   for (int i = value.size() - 1; i >= 0; i--)
   {
      int zeros_count = long_int_t::BASE_LENGTH - length(value.digits_[i]);
      
      if (i != value.size() - 1)
      {
         for (int j = 0; j < zeros_count; j++)
         {
            os << '0';
         }
      }

      os << value.digits_[i];
   }

   return os;
}

long_int_t::long_int_t(const std::vector<long long>& vector) : shift_(0)
{
   if (!vector.empty())
   {
      digits_ = vector;
   }
   else
   {
      digits_ = std::vector<long long>(1, 0);
   }
   cut_zeros();
}

void long_int_t::cut_zeros()
{
   while (digits_.size() > 1 && digits_.back() == 0)
   {
      digits_.pop_back();
   }
}

void long_int_t::normalize()
{
   for (size_t i = 0; i < size(); i++)
   {
      if (digits_[i] < 0)
      {
         long long carry = (-digits_[i]) / BASE;
         if ((-digits_[i]) % BASE != 0)
         {
            carry++;
         }

         digits_[i] += BASE * carry;
         digits_[i + 1] -= carry;
      }
      else
      {
         long long carry = digits_[i] / BASE;
         digits_[i] %= BASE;

         if (carry > 0)
         {
            if (i + 1 == size())
            {
               digits_.push_back(carry);
            }
            else
            {
               digits_[i + 1] += carry;
            }
         }
      }
   }
}

inline size_t long_int_t::size() const
{
   return digits_.size();
}

long_int_t& long_int_t::operator=(const long_int_t& value)
{
   digits_ = value.digits_;
   shift_ = value.shift_;
   return *this;
}

long long long_int_t::compare_to(const long_int_t& value) const
{
   if (size() + shift_ != value.size() + value.shift_)
   {
      if (size() + shift_ > value.size() + value.shift_)
      {
         return 1;
      }
      else
      {
         return -1;
      }
   }
        
   std::vector<long long> temp_this(size() + shift_, 0), temp_value(size() + shift_, 0);

   std::copy(digits_.begin(), digits_.end(), temp_this.begin() + shift_);
   std::copy(value.digits_.begin(), value.digits_.end(), temp_value.begin() + value.shift_);

   for (int i = temp_this.size() - 1; i >= 0; i--)
   {
      if (temp_this[i] != temp_value[i])
      {
         return temp_this[i] - temp_value[i];
      }
   }

   return 0;
}

bool long_int_t::operator==(const long_int_t& value) const
{
   return (compare_to(value) == 0);
}

bool long_int_t::operator>(const long_int_t& value) const
{
   return (compare_to(value) > 0);
}

bool long_int_t::operator!=(const long_int_t& value) const
{
   return (compare_to(value) != 0);
}

bool long_int_t::operator>=(const long_int_t& value) const
{
   return (compare_to(value) >= 0);
}

bool long_int_t::operator<(const long_int_t& value) const
{
   return (compare_to(value) < 0);
}

bool long_int_t::operator<=(const long_int_t& value) const
{
   return (compare_to(value) <= 0);
}

long_int_t& long_int_t::operator<<=(int k)
{
   shift_ += k;
   return *this;
}

long_int_t& long_int_t::operator>>=(int k)
{
   shift_ -= k;
   return *this;
}

long_int_t long_int_t::operator<<(int k)
{
   long_int_t t = *this;
   t <<= k;
   return t;
}

long_int_t long_int_t::operator>>(int k)
{
   long_int_t t = *this;
   t >>= k;
   return t;
}

long_int_t& long_int_t::operator+=(const long_int_t& value)
{
   if (size() + shift_ < value.size() + value.shift_)
   {
      digits_.resize(value.size() + value.shift_ - shift_, 0);
   }

   if (shift_ > value.shift_)
   {
      digits_.insert(digits_.begin(), shift_ - value.shift_, 0);
      shift_ = value.shift_;
   }

   size_t delta = value.shift_ - shift_;
   for (size_t i = 0; i < value.size(); i++)
   {
      digits_[i + delta] += value.digits_[i];
   }

   normalize();
   return *this;
}

long_int_t& long_int_t::operator-=(const long_int_t& value)
{
   if (shift_ > value.shift_)
   {
      digits_.insert(digits_.begin(), shift_ - value.shift_, 0);
      shift_ = value.shift_;
   }
 
   size_t delta = value.shift_ - shift_;
   size_t i;
   for (i = 0; i < value.size(); i++)
   {
      digits_[i + delta] -= value.digits_[i];
   }

   normalize();
   cut_zeros();
   return *this;
}

long_int_t& long_int_t::operator*=(long long value)
{
   if (value == 0)
   {
      *this = 0;
      return *this;
   }

   for (size_t i = 0; i < size(); i++)
   {
      digits_[i] *= value;
   }

   normalize();
   return *this;
}

long long long_int_t::find_divisor(const long_int_t& value) const
{
   if (*this < value)
   {
      return 0;
   }

   long long left = 0, right = BASE, medium;
   while (left + 1 != right)
   {
      medium = (left + right) / 2;
      if (*this < value * medium)
      {
         right = medium;
      }
      else
      {
         left = medium;
      }
   }

   return left;
}

std::pair<long_int_t, long_int_t> long_int_t::quotient_and_remainder(const long_int_t& value) const
{
   long_int_t a = *this;
   long_int_t b = value;
   b <<= (a.size() - b.size());

   std::vector<long long> result;
   while (a >= value)
   { 
      long long p = a.find_divisor(b);
      result.push_back(p);
      a -= b * p;
      b >>= 1;
   }
   reverse(result.begin(), result.end());
   if (b.shift_ + 1 > 0)
   {
      result.insert(result.begin(), b.shift_ + 1, 0);
   }

   return std::make_pair(long_int_t(result), a);
}

long_int_t& long_int_t::operator/=(const long_int_t& value)
{
   long_int_t result = *this;
   *this = result.quotient_and_remainder(value).first;
   return *this;
}

long_int_t& long_int_t::operator%=(const long_int_t& value)
{
   long_int_t result = *this;
   *this = result.quotient_and_remainder(value).second;
   return *this;
}

long_int_t long_int_t::operator+(const long_int_t& value) const
{
   long_int_t t = *this;
   t += value;
   return t;
}

long_int_t long_int_t::operator-(const long_int_t& value) const
{
   long_int_t t = *this;
   t -= value;
   return t;
}

long_int_t long_int_t::operator*(long long value) const
{
   long_int_t t = *this;
   t *= value;
   return t;
}

long_int_t long_int_t::operator/(const long_int_t& value) const
{
   long_int_t t = *this;
   t /= value;
   return t;
}

long_int_t long_int_t::operator%(const long_int_t& value) const
{
   long_int_t t = *this;
   t %= value;
   return t;
}